#include <stdlib.h>
#include "grid.h"

static struct queue{
	int row;
	int col;
}*q, pos[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

static int head, tail, num;

/*下面6个函数都是队列的操作函数*/

static int init_queue(int length){	
	q = (struct queue *)malloc(sizeof(struct queue) * length);
	head = tail = 0;
	num = length;
	return 0;
}

static int empty(void){
	if(head == tail)
		return 1;
	return 0;
}

static int destroy_queue(void){
	free(q);
	return 0;
}

static int put(struct queue ins){
	if( (head+1)%num == tail)
		return 1;

	q[head = ++head % num] = ins;
	return 0;
}

static struct queue get(void){
	struct queue tmp = {-1, -1};

	if(empty())
		return (tmp);
	else 
		return q[tail = (++tail) % num];
}

static int clean(void){
	head = tail = 0;
	return 0;
}

/*找出“前后左右”的格子。写这个只是省些代码*/
static struct queue next_pos(struct queue stand, int n, struct node **grid, int row, int col){
	stand.row += pos[n].row;
	stand.col += pos[n].col;

	if(stand.row >= 0 && stand.row < row && stand.col >= 0 && stand.col < col)
		return stand;

	stand = (struct queue){-1, -1};
	return stand;
}

/*找出路径。只是标记一下，具体显示route()返回后再处理*/
static int mark(struct node **grid, int row, int col){
	struct queue new;
	int i, j, distance;

	for(i = 0; i < row; i++)
		for(j = 0; j < col; j++)
			if(grid[i][j].end == 1)
				goto out;
	out:
	distance = grid[i][j].distance-1;
	grid[i][j].type = PICK;
	struct queue tmp = {i, j};

	while(distance >= 0){
		for(i = 0; i < 4; i++){
			new = next_pos(tmp, i, grid, row, col);
			if(new.row < 0 || new.col < 0)
				continue;

			if(grid[new.row][new.col].type == DONE && grid[new.row][new.col].distance == distance){
				distance--;
				grid[new.row][new.col].type = PICK;
				tmp = new;
				break;
			}
		}
	}
	return 0;
}

/*这个只是计算格子距离开始的格子有多远，最终的路径在mark()函数处理*/
int route(struct node **grid, int row, int col){
	int num = row * col, distance;
	struct queue new;

	init_queue (num);

	int i, j;
	for(i = 0; i < row; i++)
		for(j = 0; j < col; j++)
			if(grid[i][j].start == 1)
				goto out;

	return NOTFOUND;
	out:
	grid[i][j].distance = 0;
	grid[i][j].type = DONE;
	struct queue tmp = {i, j};
	put (tmp);

	while(!empty()){
		tmp = get();

		if(tmp.row < 0 || tmp.col < 0){
			destroy_queue();
			return ERR;
		}
		distance = grid[tmp.row][tmp.col].distance + 1;

		if(grid[tmp.row][tmp.col].end == 1){
			mark(grid, row, col);
			destroy_queue();
			return 0;
		}
		for(i = 0; i < 4; i++){
			new = next_pos (tmp, i, grid, row, col);
			if(new.row < 0 || new.col < 0 || grid[new.row][new.col].type != NORM)
				continue;
			grid[new.row][new.col].distance = distance;
			grid[new.row][new.col].type = DONE;
			put (new);
		}	
	}
	destroy_queue();
	return FAIL;
}
